googologywikiaorg-20200223-history
User blog:Deedlit11/Extending the fast-growing hierarchy to nonrecursive ordinals
The fast-growing hierarchy is of fundamental importance to googology, as it provides a measuring stick for all other large number notations, as well as making immensely large numbers itself. The definition of the fast-growing hierarchy, and other ordinal hierarchies, is an open-ended system that extends as far as fundamental sequences can be precisely defined. A natural question is how far we can extend these hierarchies. Here I will show how we can extend them to the Church-Kleene ordinal and beyond. Fundamental sequences up to \(\omega_1^{CK}\) The trick we will use to get to the Church-Kleene ordinal is the system known as Kleene's \(\mathcal{O}\). Kleene's \(\mathcal{O}\) is an ordinal notation system that maps a subset of the natural numbers to the recursive ordinals. Every recursive ordinal is represented by at least one natural number, although some ordinals will be represented by multiple natural numbers. We define a subset of the natural numbers, which we shall call notations, and a function O from the notations to the recursive ordinals as follows: 1. 0 is a notation and O(0) = 0. 2. If \(n\) is a notation with \(O(n) = \alpha\), then \(2^n\) is a notation with \(O(2^n) = \alpha + 1\). We set \(n <_O 2^n\). 3. Let \(\varphi_m (n)\) be the partial function computed by the \(m\)th Turing machine. If \(m\) is such that, for all \(n\), \(\varphi_m(n)\) is a notation and \(\varphi_m(n) <_O \varphi_m (n+1) \), then \(3 * 5^m\) is a notation, \(O(3 * 5^m) = \sup_{n \in \mathbb{N}} (O(\varphi_m(n)))\), and for all \(n, \varphi_m(n) <_O 3 * 5^m\). 4. If \(i <_O j\) and \(j <_O k\) then \(i <_O k \). Note that notations of the form \(2^n\) represent successor ordinals, and notations of the form \(3 * 5^n\) represent limit ordinals. Fortuitously, the \(m\) in \(3 * 5^m\) stands for a Turing machine that computes a sequence of notations that represent an increasing sequence of ordinals whose limit is \( O(3 * 5^m) \). That is, a notation for a limit ordinal comes with a ready made fundamental sequence! So for any recursive limit ordinal \(\alpha\), we define the fundamental sequence for \(\alpha\) as follows: Let m be the smallest natural number such that \(3 * 5^m\) is a notation for \(\alpha\). Let \(\alphan = O(\varphi_m(n))\). That's it! All that's left is to define a fundamental sequence for \(\omega_1^{CK}\) itself. Define \(f(0) = 0\), and define \(f(n+1)\) to be the smallest notation such that \(f(n+1) >_O f(n)\). Let \(\omega_1^{CK}n = O(f(n))\). To see that the limit of this sequence is the Church-Kleene ordinal, let \(\alpha\) be any recursive ordinal, and let n be a notation for \(\alpha\). Then there exists an m such that \(f(m) \le n < f(m+1)\). If \(f(m) = n\), then by the definition of \(f(m+1)\) we have \(n <_O f(m+1)\). If \(f(m) < n\), then we must have \(n \le_O f(m)\), since otherwise we would have chosen \(f(m+1) = n\). Either way, \(n <_O f(m+1)\), so \(\alpha < \omega_1^{CK}m+1\). So the fundamental sequence eventually surpasses every recursive ordinal, so the limit can only be \(\omega_1^{CK}\). Higher admissible ordinals To go beyond \(\omega_1^{CK}\), we will use oracle Turing machines. To get unique defintions, we will need a specific definition of a Turing machine with an oracle for the halting problem. We can then define a version of Kleene's \(\mathcal{O}\) where instead of regular Turing machines we use Turing machines with an oracle for the halting problem for regular Turing machines. This gives us a notation for ordinals up to \(\omega_2^{CK}\), and we define fundamental sequences for those ordinals in the exact same way as before. More generally, we can define a rank-\(\alpha\) Turing machine as follows: 1. A 0-Turing machine is a regular Turing machine. 2. An \(\alpha+1\)-Turing machine is Turing machine with an oracle for the halting problem for the \(\alpha\)-Turing machines. 3. An \(\alpha\)-Turing machine when \(\alpha\) is a limit ordinal is a Turing machine with an oracle for H(m, n), where H(m, n) is 1 when the \(n\)th rank-\(\alpham\) Turing machine halts, and 0 otherwise. (H(m, n) can be thought of as a diagonalized halting function.) The rank-\(\alpha\) Turing machine will allow us to define fundamental sequences for all ordinals \(\beta\) with \(\omega_{\alpha}^{CK} < \beta \le \omega_{\alpha+1}^{CK}\). All that remains is to define fundamental sequences for \(\omega_{\alpha}^{CK}\) where \(\alpha\) is a limit ordinal. In that case, we simply define \(\omega_{\alpha}^{CK}n = \omega_{\alphan}^{CK}\). That takes us up to the first \(\alpha\) such that \(\alpha = \omega_{\alpha}^{CK}\). In this case, we define \(\alpha0 = 1\), and \(\alphan+1 = \omega_{\alphan}^{CK}\). More generally, if \(\Phi(1, \alpha) \), is the \(\alpha\)th ordinal \(\beta\) such that \(\beta = \omega_{\beta}^{CK}\), we can define \(\Phi(1, \alpha+1) 0 = \Phi(1, \alpha) + 1\) \(\Phi(1, \alpha+1) n+1 = \omega_{\Phi(1, \alpha + 1) n}^{CK}\) \(\Phi(1, \alpha) n = \Phi(1, \alphan)\) when \(\alpha\) is a limit ordinal. Note that this definition is the same as the definition of fundamental sequences for \(\varphi(1,\alpha)\), except the base function is \(\Phi(0, \alpha) = \omega_{\alpha}^{CK}\) rather than \(\varphi(0, \alpha) = \omega^{\alpha}\). So we can continue up the Veblen hierarchy, and extend to the Extended Veblen hierarchy, the Schutte Klammersymbolen, the Bachmann notations, and so on, and we can define fundamental sequences all the way, and therefore we can extend the fast-growing hierarchy that far. Whatever the limit is, it is quite remote indeed! Category:Blog posts